package non_recursive;

public class MaxSubArray {
    private static final int[] array = {13, -3, -25, 20, -3, -16, -23, 18, 20, -7, 12, -5, -22, 15, -4, 7};

    public static void main(String[] args) {
        MaxArrayHelper currentArrayHelper = new MaxArrayHelper();
        MaxArrayHelper historyArrayHelper = new MaxArrayHelper();
        historyArrayHelper.maxSum = Integer.MIN_VALUE;
        currentArrayHelper.maxLeftIndex = 0;
        currentArrayHelper.maxSum = Integer.MIN_VALUE;
        for (int i = 0; i < array.length; i++) {
            if (currentArrayHelper.maxSum + array[i] > array[i]){
                currentArrayHelper.maxSum += array[i];
                currentArrayHelper.maxRightIndex = i;
            }else {
                currentArrayHelper.maxSum = array[i];
                currentArrayHelper.maxLeftIndex = i;
            }

            if (historyArrayHelper.maxSum < currentArrayHelper.maxSum){
                copyHelper(currentArrayHelper,historyArrayHelper);
            }
        }
        System.out.println("left index:" + historyArrayHelper.maxLeftIndex);
        System.out.println("right index:" + historyArrayHelper.maxRightIndex);
        System.out.println("max sum:" + historyArrayHelper.maxSum);
    }

    private static void copyHelper(MaxArrayHelper src,MaxArrayHelper dest){
        dest.maxSum = src.maxSum;
        dest.maxLeftIndex = src.maxLeftIndex;
        dest.maxRightIndex = src.maxRightIndex;
    }

    static class MaxArrayHelper {
        int maxLeftIndex;
        int maxRightIndex;
        int maxSum;
    }
}
